﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using Library.Linq;
using INDEX = System.UInt64;

namespace Library.Collections.Generic
{
    [DebuggerDisplay("Count={Count}")]
    public sealed class Stack<T> : IStack<T>, IStack, IClearable, IFirst<T>, IElementAt<T>, ILast<T>, IReverse<T>
    {
        struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator, IDisposable
        {
            internal Enumerator(Stack<T> stack)
            {
                this.stack = stack;
                index = -2;
                version = stack.version;
            }

            Stack<T> stack;
            long index;
            INDEX version;

            public void Dispose()
            {
                index = -1;
            }

            public bool MoveNext()
            {
                if (version != stack.version)
                    throw new InvalidOperationException();

                if (index == -2)
                    index = (long)stack.count;

                return index != -1 && --index != -1;
            }

            public T Current
            {
                get
                {
                    if (index < 0)
                        throw new InvalidOperationException();

                    return stack.data[index];
                }
            }

            public void Reset()
            {
                if (version != stack.version)
                    throw new InvalidOperationException();

                index = -2;
            }

            object System.Collections.IEnumerator.Current
            {
                get
                {
                    return Current;
                }
            }
        }
        struct EnumeratorReversed : IEnumerator<T>, IDisposable
        {
            Stack<T> stack;
            long next;
            INDEX version;

            T current;

            public EnumeratorReversed(Stack<T> stack)
                : this()
            {
                this.stack = stack;
                version = stack.version;
            }

            public void Dispose()
            {
            }

            public bool MoveNext()
            {
                if (version != stack.version)
                    throw new InvalidOperationException();

                if (next < 0)
                    return false;

                if ((INDEX)next < stack.count)
                {
                    current = stack.data[next++];
                    return true;
                }

                next = -1;
                return false;
            }

            public T Current
            {
                get { return current; }
            }

            public void Reset()
            {
                if (version != stack.version)
                    throw new InvalidOperationException();

                next = 0;
            }

            object System.Collections.IEnumerator.Current
            {
                get
                {
                    return current;
                }
            }
        }
        struct StackReversed : IStack<T>, IStack, IFirst<T>, IElementAt<T>, ILast<T>, IReverse<T>
        {
            public StackReversed(Stack<T> stack)
            {
                this.stack = stack;
            }
            internal Stack<T> stack;

            public bool Pop()
            {
                return false;
            }

            public bool Pop(out T item)
            {
                item = default(T);
                return false;
            }

            public bool Push(T item)
            {
                return false;
            }

            public bool Peek(out T item)
            {
                if (stack.count == 0)
                {
                    item = default(T);
                    return false;
                }
                item = stack.data[0];
                return true;
            }

            public bool Contains(T item)
            {
                return stack.Contains(item);
            }

            public INDEX Count
            {
                get { return stack.count; }
            }

            public IEnumerator<T> GetEnumerator(Direction direction)
            {
                if (direction == Direction.Forward)
                    return stack.GetEnumerator(Direction.Reverse);
                else
                    return stack.GetEnumerator();
            }

            System.Collections.IEnumerator Specialized.IEnumerableDirection.GetEnumerator(Direction direction)
            {
                if (direction == Direction.Forward)
                    return stack.GetEnumerator(Direction.Reverse);
                else
                    return stack.GetEnumerator();
            }

            public IEnumerator<T> GetEnumerator()
            {
                return stack.GetEnumerator(Direction.Reverse);
            }

            System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
            {
                return stack.GetEnumerator(Direction.Reverse);
            }

            public bool IsReadOnly
            {
                get { return true; }
            }

            public bool First(out T item)
            {
                if (stack.count == 0)
                {
                    item = default(T);
                    return false;
                }
                item = stack.data[0];
                return true;
            }

            public bool ElementAt(INDEX index, out T item)
            {
                if (index < stack.count)
                {
                    item = stack.data[index];
                    return true;
                }
                item = default(T);
                return false;
            }

            public bool Last(out T item)
            {
                return stack.Peek(out item);
            }

            public IEnumerable<T> Reverse()
            {
                return stack.IsReadOnly ? stack : ReadOnly.AsReadOnly(stack);
            }

            public bool Contains(T item, out INDEX index)
            {
                int n = Array.IndexOf(stack.data, item, 0, (int)stack.count);
                if (n < 0)
                {
                    index = 0;
                    return false;
                }
                index = (INDEX)n;
                return true;
            }

            public T this[INDEX index]
            {
                get
                {
                    if (index < stack.count)
                    {
                        return stack.data[index];
                    }
                    throw new IndexOutOfRangeException();
                }
            }

            public bool Pop(out object item)
            {
                item = null;
                return false;
            }

            public bool Push(object item)
            {
                return false;
            }

            public bool Peek(out object item)
            {
                item = null;
                return false;
            }

            public bool Contains(object item)
            {
                if (item is T)
                {
                    return stack.Contains((T)item);
                }
                else
                {
                    return false;
                }
            }
        }

        public Stack()
        {
            data = new T[0];
            count = 0;
            version = 0;
        }
        public Stack(INDEX capacity)
        {
            data = new T[capacity];
            count = 0;
            version = 0;
        }
        public Stack(IEnumerable<T> enumerable)
        {
            if (enumerable == null)
                throw new ArgumentNullException("enumerable");

            IStackReadOnly<T> readonlystack = enumerable as IStackReadOnly<T>;
            if (readonlystack != null)
            {
                Init(readonlystack);
            }
            else
            {
                ICountable countable = enumerable as ICountable;
                if (countable != null)
                {
                    count = countable.Count;
                    data = new T[count];
                    INDEX counter = 0;
                    foreach (var item in enumerable)
                        data[counter++] = item;
                    version = 0;
                }
                else
                {
                    data = new T[0];
                    count = 0;
                    version = 0;
                    foreach (var item in enumerable)
                        Push(item);
                }
            }
        }
        public Stack(IStackReadOnly<T> stack)
        {
            if (stack == null)
                throw new ArgumentNullException("stack");

            Init(stack);
        }
        private Stack(T[] data, INDEX count)
        {
            this.data = data;
            this.count = count;
            this.version = 0;
        }

        void Init(IStackReadOnly<T> stack)
        {
            Stack<T> other_stack = stack as Stack<T>;
            if (other_stack != null)
            {
                count = other_stack.count;
                data = new T[count];
                version = 0;
                Array.Copy(other_stack.data, data, (int)count);
            }
            else if (stack is StackReversed)
            {
                StackReversed reversed_stack = (StackReversed)stack;
                Stack<T> _stack = reversed_stack.stack;
                count = _stack.count;
                data = new T[count];
                version = 0;
                for (INDEX i = 0; i < count; ++i)
                    data[i] = _stack.data[count - i - 1];
            }
            else
            {
                data = new T[0];
                count = 0;
                version = 0;
                using (var enumerator = stack.GetEnumerator(Direction.Reverse))
                {
                    while (enumerator.MoveNext())
                    {
                        Push(enumerator.Current);
                    }
                }
            }
        }

        T[] data;
        INDEX count;
        INDEX version;

        public bool Pop()
        {
            if (count == 0) return false;
            data[--count] = default(T);
            ++version;
            return true;
        }

        public bool Pop(out T item)
        {
            if (count == 0)
            {
                item = default(T);
                return false;
            }
            item = data[--count];
            data[count] = default(T);
            ++version;
            return true;
        }

        public bool Push(T item)
        {
            if (count == (INDEX)data.Length)
            {
                Array.Resize(ref data, (int)(count == 0 ? 4 : count * 2));
            }
            data[count++] = item;
            ++version;
            return true;
        }

        public bool Peek(out T item)
        {
            if (count == 0)
            {
                item = default(T);
                return false;
            }
            item = data[count - 1];
            return true;
        }

        public bool Contains(T item)
        {
            return Array.IndexOf(data, item, 0, (int)count) >= 0;
        }

        public INDEX Count
        {
            get
            {
                return count;
            }
        }

        public bool Clear()
        {
            Array.Clear(data, 0, data.Length);
            count = 0;
            version++;
            return true;
        }

        public IEnumerator<T> GetEnumerator()
        {
            return new Enumerator(this);
        }

        public IEnumerator<T> GetEnumerator(Direction direction)
        {
            return direction == Direction.Reverse ? (IEnumerator<T>)new EnumeratorReversed(this) : (IEnumerator<T>)new Enumerator(this);
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        System.Collections.IEnumerator Library.Collections.Specialized.IEnumerableDirection.GetEnumerator(Direction direction)
        {
            return direction == Direction.Reverse ? (System.Collections.IEnumerator)new EnumeratorReversed(this) : (System.Collections.IEnumerator)new Enumerator(this);
        }

        public bool IsReadOnly
        {
            get
            {
                return false;
            }
        }

        public IStack<T> Clone()
        {
            T[] new_data = new T[count];
            Array.Copy(data, new_data, (int)count);
            return new Stack<T>(new_data, count);
        }

        public IStack<T> Clone(Access access)
        {
            T[] new_data = new T[count];
            Array.Copy(data, new_data, (int)count);

            if (access == Access.ReadWrite)
            {
                return new Stack<T>(new_data, count);
            }
            else if (access == Access.Read)
            {
                return new ReadOnly.Stack<T>(new_data, count);
            }
            else
            {
                throw new NotSupportedException();
            }
        }

        public IStack<T> Clone(Direction direction)
        {
            if (direction == Direction.Forward) return Clone();
            T[] new_data = new T[count];
            for (INDEX i = 0; i < count; ++i)
                new_data[i] = data[count - 1 - i];
            return new Stack<T>(new_data, count);
        }

        public IStack<T> Clone(Direction direction, Access access)
        {
            if (access == Access.ReadWrite)
            {
                return Clone(direction);
            }
            else if (access == Access.Read)
            {
                if (direction == Direction.Forward) return Clone(access);
                T[] new_data = new T[count];
                for (INDEX i = 0; i < count; ++i)
                    new_data[i] = data[count - 1 - i];
                return new ReadOnly.Stack<T>(new_data, count);
            }
            else
            {
                throw new NotSupportedException();
            }
        }

        bool IStack.Pop(out object item)
        {
            if (count == 0)
            {
                item = default(T);
                return false;
            }
            item = data[--count];
            data[count] = default(T);
            ++version;
            return true;
        }

        bool IStack.Push(object item)
        {
            if (!(item is T)) return false;

            if (count == (INDEX)data.Length)
            {
                Array.Resize(ref data, (int)(count + 4));
            }
            data[count++] = (T)item;
            ++version;
            return true;
        }

        bool IStackReadOnly.Peek(out object item)
        {
            if (count == 0)
            {
                item = default(T);
                return false;
            }
            item = data[count - 1];
            return true;
        }

        bool IContainer.Contains(object item)
        {
            if (!(item is T)) return false;
            return Array.IndexOf(data, item, 0, (int)count) >= 0;
        }

        bool IFirst<T>.First(out T item)
        {
            return Peek(out item);
        }

        bool IElementAt<T>.ElementAt(INDEX index, out T item)
        {
            if (count == 0 || index >= count)
            {
                item = default(T);
                return false;
            }
            item = data[(count - 1) - index];
            return true;
        }

        bool ILast<T>.Last(out T item)
        {
            if (count == 0)
            {
                item = default(T);
                return false;
            }
            item = data[0];
            return true;
        }

        IEnumerable<T> IReverse<T>.Reverse()
        {
            return new StackReversed(this);
        }
    }
}
